package com.Offer;

/*
    面试题57：和为s的数字
    输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得他们的和正好是s，如果有多对，则输出任意一对
    例如{1,2,4,7,11,15}和数字15，由于4+11=15，所以输出4和11
 */
public class demo57 {
    public static void main(String[] args) {
        int[] input = {1,2,3,4,7,11,15,17};
        FindNumbersWithSum(input,16);
        FindContinuousSequence(9);
    }

    public static void FindNumbersWithSum(int[] data,int sum){
        if (data == null || data.length < 1)
            return;
        int start = 0;
        int end = data.length-1;
        int num1 = 0;
        int num2 = 0;

        while(start < end){
            int num = data[start]+data[end];
            if(num == sum){
                System.out.println(data[start]+"+"+data[end]);
                break;
            }else if (num > sum){
                end --;
            }else{
                start++;
            }
        }
    }

    //举一反三:和为s的连续正数序列，输入一个正数s，打印出所有和为s的连续正数徐磊(至少包含两个数)
    //例如，输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出1~5,4~6和7~8
    public static void FindContinuousSequence(int sum){
        if(sum < 3)
            return;
        int small = 1;
        int big = 2;
        int middle = (1+sum)/2;
        int curSum = small+big;
        while(small < middle){
            if (curSum == sum)
                System.out.println(small+"~"+big);
            while (curSum > sum && small < middle){
                curSum -= small;
                small++;
                if (curSum == sum)
                    System.out.println(small+"~"+big);
            }
            big++;
            curSum += big;
        }
    }
}
